package week_05.sort;

public class Quick2Sort implements Sort {
    @Override
    public String toString() {
        return "Quick2Sort::";
    }

    @Override
    public void sort(int[] nums) {
        if (nums == null || nums.length < 2) return;
        quickSort(nums, 0, nums.length - 1);
    }

    private void quickSort(int[] nums, int L, int R) {

        // 大于基准的挪到右边r-- 小于基准的挪到左右l++
        // 当处理完最后一个大于基准的数据和基准做一个交换
        // 分为 小于 等于 大于基准三个区
        if (L < R) {
            // 选择一个基准进行排序挪到右边（外部有序 内部无序）
            swap(nums, L+(int) (Math.random() * (R - L + 1)), R);

            int[] privot = partition(nums, L, R);
            quickSort(nums, L, privot[0] - 1);
            quickSort(nums, privot[1] + 1, R);
        }
    }

    public int[] partition(int[] nums, int L, int R) {
        int less = L - 1;
        int more = R;
        while (L < more) {
            // 把小的数挪到左边
            if (nums[L] < nums[R]) {
                less++;
                swap(nums, less, L);
                L++;
            } else if (nums[L] > nums[R]) {
                // 把大的数挪到右边
                more--;
                swap(nums, L, more);
            } else {
                // 其他情况就是相等于基准值，不挪动
                L++;
            }
        }
        swap(nums, more, R);
        int[] privot = new int[]{less + 1, more};
        return privot;
    }


    public void swap(int[] nums, int i, int j) {
        if (i == j) return;
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;

    }
}
